package bishi.alibaba;



import java.util.ArrayList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/3/25  13:59
 */
public class _35 {
    public static int solution(TreeNode root) {
        List<Integer> zhan = new ArrayList<>();
        bianli(root,zhan);
        return zhan.get(zhan.size()-2);
    }
    public static void bianli(TreeNode root ,List<Integer> zhan){
        if (root!=null){
            bianli(root.getLeft(),zhan);
            zhan.add(root.getVal());
            bianli(root.getRight(),zhan);
        }
    }
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(20);
        TreeNode treeNode1 = new TreeNode(15);
        TreeNode treeNode2= new TreeNode(25);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(18);
        TreeNode treeNode5= new TreeNode(23);
        TreeNode treeNode6 = new TreeNode(60);
        treeNode1.setLeft(treeNode3);
        treeNode1.setRight(treeNode4);
        treeNode2.setLeft(treeNode5);
        treeNode2.setRight(treeNode6);
        treeNode.setLeft(treeNode1);
        treeNode.setRight(treeNode2);
        System.out.println(solution(treeNode));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int x) { val = x; }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}